/*
 * @lc app=leetcode.cn id=1011 lang=golang
 *
 * [1011] 在 D 天内送达包裹的能力
 */

// @lc code=start
func shipWithinDays(weights []int, days int) int {
	left := 0
	right := 0
	// 初始化运载能力上限和下限，上限：需运载货物的总重量；下限：最重的货物
	for _, weight := range weights {
		if weight > left {
			left = weight
		}
		right += weight
	}
	// 二分模板
	for left < right {
		mid := (left + right) / 2

		if isValid(weights, days, mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return right
}

// 二分答案：下限 最大重量，上限 重量和
func isValid(weights []int, days, transLimit int) bool {
	day := 1
	dayTrans := 0
	for _, weight := range weights {
		dayTrans += weight
		if dayTrans > transLimit { // 超过运载能力，天数加1
			day++
			dayTrans = weight
		}
	}
	return day <= days
}

// @lc code=end

